HashtableLookup
=================

按输入键在已排序的键表中做二分查找，写出对应字符串指针与命中标记。
算子名虽含 Hashtable，实现为有序表二分查找，要求 ``key_table`` 严格升序。

对每个下标 :math:`i = 0,\ldots,L-1`，其中 :math:`L` 为 ``input_len``：在
``key_table[0..num_keys)`` 上查找 ``input[i]``。

.. math::

    \begin{cases}
    \text{若存在 } j \text{ 使 } \mathrm{key\_table}[j]=\mathrm{input}[i], &
    \begin{aligned}
    \mathrm{output\_value}[i] &\leftarrow \mathrm{value\_table}[j] \\
    \mathrm{output\_hits}[i] &\leftarrow 1
    \end{aligned} \\[6pt]
    \text{否则}, &
    \begin{aligned}
    \mathrm{output\_value}[i] &\leftarrow \mathrm{NULL} \\
    \mathrm{output\_hits}[i] &\leftarrow 0
    \end{aligned}
    \end{cases}

未命中时 ``output_value[i]`` 写空指针 ``NULL``，而非空字符串；命中时拷贝的是
``value_table`` 中的字符串指针。

输入：
        - **input** - 待查键数组地址，元素类型 ``int32``，长度 ``input_len``
        - **key_table** - 已升序排序的键表地址，元素类型 ``int32``，长度 ``num_keys``
        - **value_table** - 字符串指针表地址，类型 ``char **``，与 ``key_table`` 一一对应
        - **num_keys** - 键表 / 值表长度
        - **input_len** - 输入键个数 :math:`L`
        - **core_mask** - 核掩码（仅共享存储版本使用）

输出：
        - **output_value** - 查找结果指针表，类型 ``char **``，长度 ``input_len``
        - **output_hits** - 命中标记，类型 ``unsigned char`` / ``uint8_t``，长度 ``input_len``；``1`` 命中，``0`` 未命中

支持平台：
        ``FT78NE``
        ``MT7004``

.. note::
        - FT78NE / MT7004 均为 int32 键，字符串指针值表
        - ``key_table`` 必须已按升序排序，否则结果不正确
        - 时间复杂度约为 :math:`O(L \log N)`，其中 :math:`N` 为 ``num_keys``

**共享存储版本:**

.. c:function:: void i32_hashtable_lookup_s(int *input, int *key_table, char **value_table, int num_keys, char **output_value, unsigned char *output_hits, int input_len, int core_mask)

**C调用示例：**

.. code-block:: c
    :linenos:
    :emphasize-lines: 13

    // MT7004 示例（共享存储多核，DDR 地址）
    void TestHashtableLookupSMC(int input_len, int core_mask) {
        int core_id = get_core_id();
        int logic_core_id = GetLogicCoreId(core_mask, core_id);
        int core_num = GetCoreNum(core_mask);
        int *input = (int *)0x82000000;
        int *key_table = (int *)0x82800000;
        char **value_table = (char **)0x83000000;
        char **output_value = (char **)0x84000000;
        unsigned char *output_hits = (unsigned char *)0x85000000;
        int num_keys = input_len / 8;
        sys_bar(0, core_num);
        i32_hashtable_lookup_s(input, key_table, value_table, num_keys, output_value, output_hits, input_len, core_mask);
    }

    void main() {
        int core_mask = 0b1111;
        TestHashtableLookupSMC(256, core_mask);
    }

**私有存储版本:**

.. c:function:: void i32_hashtable_lookup_p(int *input, int *key_table, char **value_table, int num_keys, char **output_value, unsigned char *output_hits, int input_len)

**C调用示例：**

.. code-block:: c
    :linenos:
    :emphasize-lines: 9

    // MT7004 示例（私有存储单核，AM 地址）
    void TestHashtableLookupAM(int input_len) {
        int *input = (int *)0x10010000;
        int *key_table = (int *)0x10020000;
        char **value_table = (char **)0x10030000;
        char **output_value = (char **)0x10040000;
        unsigned char *output_hits = (unsigned char *)0x10050000;
        int num_keys = input_len / 8;
        i32_hashtable_lookup_p(input, key_table, value_table, num_keys, output_value, output_hits, input_len);
    }

    void main() {
        TestHashtableLookupAM(256);
    }